home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Stacks / Updates⁄New / TEXAS for BMUG / C progs / qndxr.2 ƒ / zqsort.2.c < prev   
Encoding:
C/C++ Source or Header  |  1987-11-03  |  2.2 KB  |  97 lines  |  [TEXT/KAHL]
  1. /* file zqsort.c -- by ^z, 870823-...
  2.  * my quicksort to sort out the ptr array ... based, at least initially,
  3.  * on the Lightspeed C library qsort routine, specialized to the task
  4.  * at hand here ...
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include <strings.h>
  9. #include <proto.h>
  10. #include "qndxr.2.h"
  11.  
  12. /*  sort elements "first" through "last" */
  13.  
  14. void zqsort (first, last)
  15.   register char **first, **last;
  16.   {
  17.     register char **i, **j, *tmp;
  18.  
  19.     while (last - first > 1)
  20.       {
  21.         i = first;
  22.         j = last;
  23.         for (;;)
  24.           {
  25.             while (++i < last && compare_ptrs (i, first) < 0)
  26.                 ;
  27.             while (--j > first && compare_ptrs (j, first) > 0)
  28.                 ;
  29.             if (i >= j)
  30.                  break;
  31.              tmp = *i;
  32.              *i = *j;
  33.              *j = tmp;
  34.           }
  35.         tmp = *first;
  36.         *first = *j;
  37.         *j = tmp;
  38.         if (j - first < last - (j + 1))
  39.           {
  40.             zqsort (first, j);
  41.             first = j + 1;
  42.           }
  43.         else
  44.           {
  45.             zqsort (j + 1, last);
  46.             last = j;
  47.           }
  48.       }
  49.   }
  50.  
  51.  
  52. /* function to compare two index ptrs and give a result appropriate
  53.  * for quicksort to use in alphabetizing them....
  54.  *
  55.  * Since the words pointed to have already been turned into all capital
  56.  * letters and delimiters have been filtered out, simply doing zstrcmp()
  57.  * for KEY_LENGTH letters works fine!
  58.  *
  59.  * Slight modification to make the quicksort stable:  if two words tie,
  60.  * then we want to compare their pointers to make the lesser one come
  61.  * out first in the sort ...
  62.  */
  63.  
  64. int compare_ptrs (p1, p2)
  65.   register char **p1, **p2;
  66.   {
  67.     register int diff;
  68.     
  69.     diff = zstrcmp (*p1, *p2);
  70.     if (diff == 0)
  71.         diff = ((*p1 - *p2) > 0) ? 1 : -1;
  72.     return (diff);
  73.   }
  74.  
  75.  
  76.  
  77. /* my function to compare two strings and give a result as to who is
  78.  * alphabetically earlier.  Note that this is almost the same as strncmp()
  79.  * with the fixed value of KEY_LENGTH as the maximum comparison distance,
  80.  * except that I must be sure to mask the characters to make them positive
  81.  * (since we want to be able to handle the non-ASCII funny letters in
  82.  * the Apple character set properly/consistently).  If the masking isn't
  83.  * done, then inconsistent results can occur with those non-ASCII chars!
  84.  */
  85.  
  86. int zstrcmp (s1, s2)
  87.   register char *s1, *s2;
  88.   {
  89.     register int n = KEY_LENGTH;
  90.     
  91.     for (; --n && ((*s1 & 0xFF) == (*s2 & 0xFF)); s1++, s2++)
  92.         if (!*s1) break;
  93.         
  94.     return ((*s1 & 0xFF) - (*s2 & 0xFF));
  95.   }
  96.  
  97.